This invention relates generally to targeted item delivery with inventory management, such as targeted advertising with quotas, and more specifically to reducing noise in a cluster-based approach for such targeted advertising with quotas.
The Internet has become increasingly popular with end users, to the extent that advertisers have become attracted to this new medium. A typical type of Internet ad is known as the banner ad, which is generally displayed on the top of each web page. Operators for popular news and other sites, for example, can increase revenue by selling banner ad space to advertisers.
Frequently, advertisers choose sites to pay for banner ad space based on two criteria. First, advertisers pay to have their ads shown to specific types of people. For example, a golf store might want to have its ads shown on a sports-related page, or to people who are likely to be interested in golf based on their browsing history. Second, advertisers pay to have their ads served in such a way that the ads are likely to be xe2x80x9cclicked onxe2x80x9d by a user, so that the user will be transported to the advertiser""s web site. One way to increase revenue generated from web advertising is thus to increase the xe2x80x9cclick throughxe2x80x9d rate of the ads shown; sites with higher click-through rates can likely charge more to those advertisers who are interested in attracting people to their web sites. The click-through rate of an ad is the percentage of times a user clicks on the ad to be transported to the advertiser""s web site, against the number of times the ad is shown. Advertisers in need of advertising are thus attracted to sites that generate click through, and are usually willing to pay extra to those sites that can deliver increased click through.
One way to increase click through is by targeted advertising. Targeted advertising is the practice of showing ads to individuals based on information about them, such as their web browsing history and demographics, to increase the click-through rate. A difficulty with targeted advertising in the context of web advertising, as well as other advertising environments, is that simply showing each user the ad that will most likely be clicked will typically not be a valid approach. In particular, sites sell ad space to many different advertisers, and all of those contracts must be fulfilled regardless of the click-through rates of the individual ads. Consequently, targeted-advertising approaches must explicitly take into account the number of times that each ad needs to be shown.
Targeted advertising with quotas is one type of process that can generally be referred to as targeted delivery of items with inventory management. Targeted delivery of items with inventory management can itself be generally defined as having an inventory of an item available, such that its inventory is desirably managed to produce an optimal result, such as maximum revenue. For example, in the case of targeted advertising, there is a limited number of ads that can be shown, such that the display of ads to users is desirably managed so that the xe2x80x9cclick throughxe2x80x9d rate of the ads is maximized. Another type of inventory management is product or service placement in electronic commerce contexts.
In the pending provisional patent application which the present application has claimed the benefit of, and the pending regular patent application which the present application is a continuation-in-part (CIP) of, a linear program can be used to provide for targeted advertising with quotas. The numbers used to determine the xe2x80x9cclick throughxe2x80x9d rate of the ads to be shown can be statistical estimates from past performance. In at least some cases, these statistical estimates are susceptible to noise, which can be amplified by the linear program, reducing the effectiveness of both the linear program and of the targeted advertising provided by the linear program. For this and other reasons, therefore, there is a need for the present invention.
The invention relates to the reduction of noise within a cluster-based approach to targeted advertising with quotas. In one embodiment, a computer-implemented method allocates each of a number of ads to one or more of a number of clusters. The allocation is made based on a predetermined criterion accounting for at least a quota for each ad and a constraint for each cluster. The former in one embodiment refers to the number of times an ad must be shown. The latter in one embodiment refers to the number of times a given group of web pagesxe2x80x94viz., a clusterxe2x80x94is likely to be visited by users, and hence is the number of times ads can be shown in a given cluster. The invention is not limited to any particular definition of what constitutes a cluster, however. The method selects an ad for the current cluster a user is in from the ads allocated to that cluster, and then displays the ad.
Embodiments of the invention employ one or more of several different approaches to reduce noise within the data that may affect the allocation. In one embodiment, probabilities for the ads, where the ads can generally be referred to as items, are discretized into a predetermined number of groups, where the mean for the group that a particular probability has been discretized into can be substituted for the particular probability when the ads are being allocated. The discretization introduces the potential that many solutions may be equally good for the resulting allocation, such that a second optimization may also be performed. In cases where this optimization is difficult to solve, a greedy algorithm approximation of this optimization can be used as well. In another embodiment, the probabilities for the ads are decreased by a power function of the variances for them. This is accomplished so that the allocation does not rely as much on probability estimates that have large variances, which indicate that these estimates have more noise than other probability estimates.
In a third embodiment, allocation of ads to page groups, where page groups are referred to generally as clusters, is not changed unless the sample sizes used to determine the corresponding probabilities for those ads is greater than a threshold. This is accomplished so that allocation is not based on probability estimates determined from low sample sizes, which may not be as accurate as estimates determined from high sample sizes, for example. In a fourth embodiment, after allocation is performed a first time by, for example, using a linear program, a predetermined number of ads are removed, and reallocation is performed by, for example, again using a linear program, to fill the newly emptied slots that result from removal. In this way, ads that are considered poor by some measurement can be eliminated from the allocation into clusters. Each of the embodiments can be performed independently, or in conjunction with any of the other embodiments.